This application claims priority from Korean Patent Application No. 10-2002-87243, filed on Dec. 30, 2002, the entire contents of which are hereby incorporated by reference.
1. Field of the Invention
The present invention relates to a public-key cryptographic system, and more particularly, to a Montgomery modular multiplier.
2. Description of the Related Art
Cryptographic systems are used in communications achieved through smart cards, IC cards, and the like and have developed from secret-key cryptographic systems to public-key cryptographic systems. In a secret-key cryptographic system, two users must share an identical secret key in order to communicate with each other. Hence, key management and digital signing, which are based on a secret-key cryptographic system, are difficult. On the other hand, in a public-key cryptographic system, a secret key is secured by each user and any user who knows the public key of another party can communicate with that party, facilitating a process of convenient secret communications.
Examples of a public-key cryptographic system include Ron Rivest, Adi Schamir, and Len Adleman (RSA), Diffie-Hellman, a Digital Signature Algorithm (DSA), an Elliptic Curve Cryptosystem (ECC), and the like. Since a public-key cryptographic system performs modular multiplication to achieve a modular exponentiation operation, the system must adopt a modular multiplier.
A Montgomery modular multiplication algorithm, known as the most effective modular multiplication algorithm, can be expressed in pseudo code, as in Algorithm 1 below:
[Algorithm 1]Stimulus:  A = (an-1 an-2 ... a1 a0)2, and A < M  B = (bn-1 bn-2 ... b1 b0)2, and B < M  M = (mn-1 mn-2 ... m1 m0)2, and M is odd.Response:  S = (Sn Sn-1 Sn-2 ... S1 S0)2 ≡ ABR−1 (mod M)Method:  S: = 0For i: = 0 to n-1 do  qi: = s0 XOR (bi AND a0)  S: = (S + biA + qiM)/2endfor
That is, in Algorithm 1, a final S (sum) (in Algorithm 1, carry is expressed as Sn) that is calculated in a “for” loop is congruent to ABR−1 (mod M). Here, “R−1” is an inverse number of R modular-multiplied for “mod M”. When R is equal to 2n, “(R*R−1) mod M” is equal to 1.
The Montgomery modular multiplication algorithm performs only multiplications on given numbers A, B, and M, without using divisions, and is faster than other algorithms. Hence, the Montgomery modular multiplication algorithm is widely used in implementing public-key cryptographic systems, which require a modular exponentiation operation.
Conventional Montgomery modular multipliers based on a Montgomery modular multiplication algorithm are classified as a parallel multiplier, which uses a carry propagation adder as a basic accumulator, or a serial multiplier, which uses a 3-2 (3-input to 2-output) compressor (i.e., a carry save adder made up of full adders) as a basic accumulator.
A carry propagation adder requires a carry-propagation delay time on a clock-by-clock basis to propagate a carry upon every addition of multiple bits. Since the carry propagation adder cannot increase the carry-propagation delay time without limit, multiplication of numbers represented by 32 bits or more is difficult. In other words, the carry propagation adder has a larger power-delay product than in a carry save adder. The multiplication of a 32-bit number by a 32-bit number must be repeated in order to perform a multiplication of numbers represented by 32 bits or more.
Since a serial multiplier that uses a carry save adder uses a 3-2 compressor (i.e., full adders), there are no problems of a propagation delay time, but the serial multiplier with the carry save adder is not easily implemented in hardware. The 3-2 compressor removes the propagation delay time by performing all additions on each bit at as many clock pulses as the number of bits. In other words, in a Montgomery modular multiplication algorithm such as Algorithm 1, the four words carry, S, biA, and qiM must be summed. However, the 3-2 compressor can only receive 3 words, and accordingly, a problem arises in that the two main input words biA and qiM need to be summed in advance. Also, when the 3-2 compressor performs addition, it must receive carry, S, and one of the four words (namely, carry, S, biA, and qiM) and accordingly, requires a 4:1 multiplexer to select one of the four words.